package com.linyaonan.leetcode.sword_to_offer._57_2;

import java.util.LinkedList;
import java.util.List;

/**
 * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 *
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：target = 9
 * 输出：[[2,3,4],[4,5]]
 * 示例 2：
 *
 * 输入：target = 15
 * 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
 *  
 *
 * 限制：
 *
 * 1 <= target <= 10^5
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {
    public int[][] findContinuousSequence(int target) {
        int p = target * 2;
        int cur = 2;

        LinkedList<int[]> r = new LinkedList<>();
        boolean flag = true;
        while (cur <= target && flag) {
            if (p % cur == 0) {
                int count = p / cur;
                int[] tt = new int[cur];
                int start;
                // 奇数
                if ((cur & 1) == 1) {
                    if (count != target / cur) {
                        continue;
                    }
                    start = (count / 2) - (cur / 2);

                } else {
                    if (count >= target / cur) {
                        continue;
                    }
                    // 偶数
                    start = (count / 2) - (cur / 2) + 1;
                }
                if (start <= 0) {
                    flag = false;
                    continue;
                }
                for (int i = 0; i < tt.length; i++) {
                    tt[i] = start++;
                }
                r.addFirst(tt);
            }

            cur++;
        }

        System.out.println(r);
        int[][] res = new int[r.size()][];
        for (int i = 0; i < res.length; i++) {
            res[i] = r.get(i);
        }

        return res;
    }

    private boolean check(int start, int count, int t) {
        return (start + start + count - 1) * count == t * 2;
    }
}